﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<iostream>
#include<unordered_map>
#include<algorithm>
using namespace std;
int findMaxLength(vector<int>& nums) {
    // 哈希表记录每个前缀和首次出现的索引位置
    unordered_map<int, int> prefix_map;
    // 初始化：前缀和为0出现在索引-1（虚拟起点，处理从首元素开始的子数组）
    prefix_map[0] = -1;
    int max_len = 0;   // 记录最大子数组长度
    int sum = 0;       // 当前前缀和（0视为-1，1视为+1）

    for (int i = 0; i < nums.size(); ++i) {
        // 将0转换为-1，1转换为+1，问题转化为求"和为0的最长子数组"
        sum += (nums[i] == 0) ? -1 : 1;

        // 检查当前前缀和是否已存在
        if (prefix_map.find(sum) != prefix_map.end()) {
            // 存在：当前索引与首次出现的索引之间的子数组和为0（0和1数量相等）
            max_len = max(max_len, i - prefix_map[sum]);
        }
        else {
            // 不存在：记录当前前缀和及其索引，保留首次出现位置以获取最长子数组
            prefix_map[sum] = i;
        }
    }

    return max_len;  // 返回最大长度
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty())
        return {};
    sort(intervals.begin(), intervals.end(),
        [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });

    vector<vector<int>> merged;     // 存储合并后的区间
    merged.push_back(intervals[0]); // 初始化第一个区间

    for (int i = 1; i < intervals.size(); ++i) {
        vector<int>& last = merged.back(); // 当前已合并的最后一个区间
        int curr_start = intervals[i][0];
        int curr_end = intervals[i][1];

        if (curr_start <= last[1]) {
            // 有重叠，合并区间（取最大结束点）
            last[1] = max(last[1], curr_end);
        }
        else {
            // 无重叠，直接加入新区间
            merged.push_back(intervals[i]);
        }
    }

    return merged;
}
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
    int m = mat.size(), n = mat[0].size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    // 1. 预处理前缀和矩阵
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] +
            mat[i - 1][j - 1];
    // 2. 使⽤
    vector<vector<int>> ret(m, vector<int>(n));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
        {
            int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
            int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
            ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] +
                dp[x1 - 1][y1 - 1];
        }
    return ret;
}
int tribonacci(int n) {
    if (n == 0)return 0;
    if (n == 1 || n == 2)return 1;
    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    return dp[n];
}